%%%-------------------------------------------------------------------
%%% File    : p24.erl
%%% Author  : Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% A permutation is an ordered arrangement of objects. For example, 3124 
%%% is one possible permutation of the digits 1, 2, 3 and 4. If all of the 
%%% permutations are listed numerically or alphabetically, we call it 
%%% lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
%%% 
%%% 012   021   102   120   201   210
%%% 
%%% What is the millionth lexicographic permutation of the digits 
%%% 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
%%% 
%%%
%%% Created : 10 Dec 2008
%%%-------------------------------------------------------------------
-module(p24).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------
solution(N, DigitsCount) ->
    Digits = lists:seq(0, DigitsCount - 1),
    permutation(N - 1, DigitsCount - 1, Digits, []).

%%====================================================================
%% Internal functions
%%====================================================================
%Generate the Ith permutation of N digits
permutation(_, _, [], Acc) -> lists:reverse(Acc);
permutation(I, N, Digits, Acc) ->
    Fac = factorial(N),
    Div = I div Fac,
    {Digit, NewDigits} = pop(Digits, Div + 1),
    Rem = I rem Fac,
    permutation(Rem, N - 1, NewDigits, [Digit|Acc]). 

%Remove and return the item at index Index from the list.
pop(List, Index) ->
    pop(List, 1, Index, []).

pop([], _, _, _)->
    exit(not_found);
pop([H|T], I, I, Acc)->
    {H, lists:reverse(Acc) ++ T};
pop([H| T], I, Index, Acc)->
    pop(T, I + 1, Index, [H|Acc]).

factorial(0) ->
    1;
factorial(N) ->
    N*factorial(N-1).
